package interview.huawei.tjt.training.dongtaiguihua;

import java.util.Scanner;

/**
 * 给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。
 *
 * 示例:
 *
 * nums = [1,2,3] target = 4
 *
 * 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1)
 *
 * 请注意，顺序不同的序列被视作不同的组合。
 *
 * 因此输出为 7。
 */
public class CombinationSum4 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] strings = sc.nextLine().split(",");
        int target = sc.nextInt();
        int[] nums = new int[strings.length];
        for (int i = 0; i < nums.length; i ++) {
            if (!strings[i].equals("")) {
                nums[i] = Integer.parseInt(strings[i]);
            }
        }
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int i = 0; i <= target; i ++) {
            for (int j = 0; j < nums.length; j ++) {
                if ( i >= nums[j] ) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        System.out.println(dp[target]);
    }

}
